<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>01-二叉搜索树（BST）</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(key) {
          this.key = key // 当前键值
          this.left = null // 大于key的元素
          this.right = null // 小于key的元素
        }
      }
      class BinarySearchTree {
        constructor() {
          this.root = null
        }
        // 插入一个值
        insert(key) {
          if (this.root == null) {
            this.root = new Node(key)
          } else {
            this.insertNode(this.root, key)
          }
        }
        insertNode(node, key) {
          if (key < node.key) {
            // 新节点的键小于当前
            if (node.left == null) {
              node.left = new Node(key)
            } else {
              this.insertNode(node.left, key)
            }
          } else {
            // 新节点的键大于当前
            if (node.right == null) {
              node.right = new Node(key)
            } else {
              this.insertNode(node.right, key)
            }
          }
        }

        // 中序遍历（从小到大）
        inOrderTraverse(callback) {
          this.inOrderTraverseNode(this.root, callback)
        }
        inOrderTraverseNode(node, callback) {
          if (node != null) {
            this.inOrderTraverseNode(node.left, callback)
            callback(node.key)
            this.inOrderTraverseNode(node.right, callback)
          }
        }

        // 先序遍历(先本身，再后代)
        preOrderTraverse(callback) {
          this.preOrderTraverseNode(this.root, callback)
        }
        preOrderTraverseNode(node, callback) {
          if (node != null) {
            callback(node.key)
            this.preOrderTraverseNode(node.left, callback)
            this.preOrderTraverseNode(node.right, callback)
          }
        }

        // 后序遍历(先后代，再本身)
        postOrderTraverse(callback) {
          this.postOrderTraverseNode(this.root, callback)
        }
        postOrderTraverseNode(node, callback) {
          if (node != null) {
            this.postOrderTraverseNode(node.left, callback)
            this.postOrderTraverseNode(node.right, callback)
            callback(node.key)
          }
        }

        // 搜索最小值
        min() {
          return this.minNode(this.root)
        }
        minNode(node) {
          let current = node
          while (current != null && current.left != null) {
            current = current.left
          }
          return current
        }

        // 搜索最大值
        max() {
          return this.maxNode(this.root)
        }
        maxNode(node) {
          let current = node
          while (current != null && current.right != null) {
            current = current.right
          }
          return current
        }

        // 搜索一个特定的值
        search(key) {
          return this.searchNode(this.root, key)
        }
        searchNode(node, key) {
          if (node == null) {
            return false
          }
          if (key < node.key) {
            return this.searchNode(node.left, key)
          } else if (key > node.key) {
            return this.searchNode(node.right, key)
          } else {
            return true
          }
        }

        // 移除一个节点
        remove(key) {
          this.root = this.removeNode(this.root, key)
        }
        removeNode(node, key) {
          if (node == null) {
            return null
          }
          if (key < node.key) {
            node.left = this.removeNode(node.left, key)
            return node
          } else if (key > node.key) {
            node.right = this.removeNode(node.right, key)
            return node
          } else {
            // 键等于node.key
            // 情况一
            if (node.left == null && node.right == null) {
              node = null
              return node
            }
            // 情况二
            if (node.left == null) {
              node = node.right
              return node
            } else if (node.right == null) {
              node = node.left
              return node
            }
            // 情况三
            const rightMinNode = this.minNode(node.right)
            node.key = rightMinNode.key
            node.right = this.removeNode(node.right, rightMinNode.key)
            return node
          }
        }
      }

      // 代码测试
      var tree = new BinarySearchTree()
      tree.insert(11)
      tree.insert(7)
      tree.insert(15)
      tree.insert(5)
      tree.insert(3)
      tree.insert(9)
      tree.insert(8)
      tree.insert(10)
      tree.insert(13)
      tree.insert(12)
      tree.insert(14)
      tree.insert(20)
      tree.insert(18)
      tree.insert(25)
      tree.insert(6)

      const printNode = (value) => console.log(value)
      tree.inOrderTraverse(printNode)
      // tree.preOrderTraverse(printNode)
      // tree.postOrderTraverse(printNode)

      // console.log(tree.min())
      // console.log(tree.max())

      // console.log(tree.search(1) ? '1 found' : '1 not fount')
      // console.log(tree.search(18) ? '18 found' : '18 not fount')
    </script>
  </body>
</html>
